Razonamiento
Es un método de demostración que se utiliza cuando se trata de establecer la veracidad de una lista infinita de proposiciones. El método es bastante natural para usarse en una variedad de situaciones en la ciencia de la computación.
Base de la Inducción
a. 1 es un número natural.
b. si n es un número natural, entonces n+1 también es número narutal.
El principio de inducción es usar esta definición para probar cosas. Podemos definirlo de varias maneras:
I. Si A es un subconjunto de los números naturales tal que:
a. 1 pertenece a A
b. si n pertenece a A, entones n + 1 pertenece a A
Entonces A contiene todos los naturales.
II. Si una propiedad P de un subconjunto de los números naturales cumple que:
a. P es cierta para 1
b. si P es cierta para n, entonces P es cierta para n + 1.
Entonces P es cierta ara todos los naturales.
Analogía de los Dominó
Si ponemos todos nuestros dominós parados en una fila, necesitamos sólo asegurarnos de dos cosas para que se caigan:
a) Que exista al menos un dominó que se caiga.
b) Que si un dominó cae, empuja al siguiente.
Los números naturales son como un conjunto infinito pero ordenado de dominós, donde cada dominó tiene escrito un número. Las pruebas por inducción son como ordenar nuestros dominós parados en una fila y ver si es
posible empujar alguno para que se caigan todos.
a) El caso base es asegurarse de que exista un primer dominó que se caiga.
b) El paso inductivo es suponer que si cumple para algún entero, cumple para el siguiente.
Comprobando con 1
Comprobando con K
Comprobando con K+1
Ejemplo:
Practica lo Aprendido
Comprobar por inducción matemática la siguiente expresión:
